package org.lql.algo.codecrush.hot100.linked;

import org.lql.algo.common.ListNode;

/**
 * @author: liangqinglong
 * @date: 2025-10-11 11:19
 * @description: 21. 合并两个有序链表 <a href="https://leetcode.cn/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class MergeTwoLists {

	public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
		if (list1 == null) {
			return list2;
		}
		if (list2 == null) {
			return list1;
		}
		ListNode head = new ListNode(-1);
		ListNode cur = head;
		while (list1 != null && list2 != null) {
			if (list1.val < list2.val) {
				cur.next = list1;
				list1 = list1.next;
			} else {
				cur.next = list2;
				list2 = list2.next;
			}
			cur = cur.next;
		}
		if (list1 != null ) {
			cur.next = list1;
		}
		if (list2 != null) {
			cur.next = list2;
		}
		return head.next;
	}
}
